package com.googlecode.gaal.suffix.algorithm.impl;

import com.googlecode.gaal.data.api.IntSequence;
import com.googlecode.gaal.suffix.algorithm.api.LcpTableBuilder;

/**
 * Kasai et al algorithm for getting lcp lrray.
 * 
 * @author Alex Kislev
 * 
 */
public class KasaiLcpTableBuilder implements LcpTableBuilder {
    @Override
    public int[] buildLcpTable(int[] suffixTable, IntSequence text) {
        int n = suffixTable.length - 1;
        int[] lcp = new int[n + 1];
        int[] rank = new int[n + 1];
        for (int i = 0; i < n; i++) {
            rank[suffixTable[i]] = i;
        }
        int h = 0;
        for (int i = 0; i < n; i++) {
            int k = rank[i];
            if (k == 0) {
                lcp[k] = -1;
            } else {
                int j = suffixTable[k - 1];
                while (i + h <= n && j + h <= n && text.get(i + h) == text.get(j + h)) {
                    h++;
                }
                lcp[k] = h;
            }
            if (h > 0) {
                h--;
            }
        }
        return lcp;
    }

}
